#ifndef __HASH_H
#define __HASH_H

using namespace std;

#include "constants.h"
#include <stdlib.h>
#include <iostream>

static unsigned long prime_list[]={
  2,3,5,11,23,53,73,101,127,151,173,211,223,251,271,307,331,353,373,401,
  421,449,479,503,523,557,571,601,631,653,673,701,727,751,773,809,823,
  853,877,907,929,953,977,1009,1097,1201,1301,1409,1511,1601,1709,1801,
  1901,2003,2111,2203,2309,2411,2503,2609,2707,2801,2903,3001,3109,3203,
  3301,3407,3511,3607,3701,3803,3907,4001,4111,4201,4327,4409,4507,4603,
  4703,4801,4903,5003,5101,5209,5303,5407,5501,5591,5701,5801,5903,6007,
  6101,6203,6301,6397,6521,6607,6701,6803,6907,7001,7103,7207,7307,7411,
  7507,7603,7703,7817,7901,8009,8101,8209,8311,8419,8501,8599,8699,8803,
  8923,9001,9103,9203,9311,9403,9511,9601,9719,9803,9901,10007,11003,12049,
  13033,14009,15013,16001,17011,18013,19001,20011,21089,22003,23003,24001,
  25013,26003,27011,28001,29009,30011,31013,32003,33029,34019,35023,36011,
  36943,37963,38993,40009,41051,42013,43003,44087,45083,46147,47161,48179,
  49169,50119,51001,52009,53069,54059,55001,56003,57037,58013,59023,60029,
  61091,62137,63277,64223,65089,66029,67103,68059,69193,70249,71059,72031,
  73039,74161,75011,76031,77153,78139,79043,80077,81049,82073,83203,84589,
  85447,86477,87281,88379,89101,90071,91159,92083,93053,94111,95153,96181,
  97301,98041,99109,100003};
static int prime_list_length = 222;

// Find the first prime number bigger than the size
int find_prime(int size)
{
  for(int i = 0; i < prime_list_length; i++)
    if (prime_list[i] > size)
      return prime_list[i];
}


template <class E>
class HashEntry
{
 public:
  int key;
  E* data;
  Estate state;
  HashEntry<E>* next;

  // Constructors/Destructors
  HashEntry();
  HashEntry(int, E*);
  HashEntry(const HashEntry<E>&);

  // Operators
  HashEntry<E>* operator=(const HashEntry<E>&);

};

template <class E>
HashEntry<E>::HashEntry()
{
  key = 0;
  state = EMPTY;
  next = NULL;
}

template <class E>
HashEntry<E>::HashEntry(int k, E* e)
{
  key = k;
  data = e;
  state = VALID;
  next = NULL;
}


template <class E>
HashEntry<E>::HashEntry(const HashEntry<E>& he)
{
  key = he.key;
  data = he.data;
  state = he.state;
  next = he.next;
}

template <class E>
HashEntry<E>* HashEntry<E>::operator=(const HashEntry<E>& he)
{
  key = he.key;
  data = he.data;
  state = he.state;
  next = he.next;
}



template <class E>
class HashTable
{
 public:
  HashEntry<E>* table;
  int size;
  int current_index;
  HashEntry<E>* current_entry;

 public:
  // Constructors/Destructors
  HashTable();
  HashTable(int);
  HashTable(const HashTable<E>&);
  ~HashTable();

  // Functions
  int insert(int, E*);
  int remove(int);
  E* lookup(int);

  // Iterator tools
  void begin();
  E* get();
};

template <class E>
HashTable<E>::HashTable()
{
  size = find_prime(DEFSIZE);
  table = new HashEntry<E>[size];
}

template <class E>
HashTable<E>::HashTable(int s)
{
  size = find_prime(s);
  table = new HashEntry<E>[size];
}

template <class E>
HashTable<E>::HashTable(const HashTable<E>& ht)
{
  size = ht.size;
  table = new HashEntry<E>[size];
  memcpy(table, ht.table, ht.size*sizeof(HashEntry<E>));

}

template <class E>
HashTable<E>::~HashTable()
{
  delete[] table;
  table = NULL;
}

template <class E>
int HashTable<E>::insert(int key, E* e)
{
  if (table[key % size].state == EMPTY)
    {
      table[key % size] = *(new HashEntry<E>(key, e));
      return TRUE;
    }
  else
    {
      HashEntry<E>* h = new HashEntry<E>(key, e);
      HashEntry<E>* t = &table[key % size];
      while (t && t->next && t->key != key)
	{
	  t = t->next;
	}
      if (t && t->key != key)
	{
	  t->next = h;
	  return TRUE;
	}
      else
	return FALSE;
    }
  return FALSE;
}

template <class E>
int HashTable<E>::remove(int key)
{
  HashEntry<E>* t = &table[key % size], *prev = NULL;
  while (t)
    {
      if (t->key == key)
	{
	  if (prev == NULL)
	    {
	      if (t->next) 
		table[key % size] = *(t->next);
	      else
		table[key % size].state = EMPTY;
	    }
	  else
	    {
	      prev->next = t->next;
	    }
	  if (prev)
	      delete t;
	  t = NULL;
	  return TRUE;
	}
      prev = t;
      t = t->next;
    }
  return FALSE;
}

template <class E>
E* HashTable<E>::lookup(int key)
{
  HashEntry<E>* t = &table[key % size];
  while (t)
    {
      if (t->state == VALID && t->key == key)
	return (t->data);
      t = t->next;
    }
  return NULL;
}


template <class E>
void HashTable<E>::begin()
{
  current_index = -1;
  current_entry = NULL;
}

template <class E>
E* HashTable<E>::get()
{
  if (current_entry == NULL)
    {
      do{
	current_index++;
      }
      while(current_index < size && table[current_index].state != VALID);
      if (current_index == size)
	return NULL;
      current_entry = &table[current_index];
    }
  E* ptr = current_entry->data;
  int key = current_entry->key;
  current_entry = current_entry->next;
  return ptr;
}

#endif
